package MySearch;

import MyBinaryTree.BiTree;

public class BSTree {
    // 二叉排序树的根节点
    private BiTreeNode root;
    public BSTree(){
        this.root = null;
    }

    public BSTree(BiTreeNode root) {
        this.root = root;
    }

    public Object searchBST(int key){
        return searchBST(root, key);
    }
    public Object searchBST(BiTreeNode p, int key){
        if(p==null){
            return null;
        }else {
            if(key==p.key){
                return p.data;
            }else if(key<p.key){
                // key 小于根节点 去左孩子寻找数据
                return searchBST(p.lchild, key);
            }else if(key > p.key){
                // key 大于根节点 去右孩子寻找数据
                return searchBST(p.rchild, key);
            }
            // 这里压根进不来
            return null;
        }
    }

    /**
     * 二叉排序树的插入算法
     * @param key    关键字
     * @param data   节点值
     * @return
     */
    public boolean insertBST(int key, Object data){
        BiTreeNode p = new BiTreeNode(data, key);
        return insertBST(root, p);
    }

    /**
     * 二叉排序树插入算法
     * @param r 待插入位置的节点
     * @param p 待叉入的节点
     * @return
     */
    public boolean insertBST(BiTreeNode r, BiTreeNode p){
        if(r == null){
            r = p;
            return true;
        }else if(r.key < p.key){
            // 如果当前节点的值小于 待插入节点的值 往右子树寻找对应节点
            return insertBST(r.rchild, p);
        }else{
            // 如果当前节点的值小于 待插入节点的值 往右子树寻找对应节点
            return insertBST(r.lchild, p);
        }
    }

    public Object removeBST(int key){
        // 删除关键字为key的节点
        return removeBST(root, key, null);
    }

    /**
     * 二叉排序树删除算法实现
     * @param p  根节点
     * @param key 待删除节点关键词
     * @param parent 父亲节点
     * @return
     */
    public Object removeBST(BiTreeNode p, int key, BiTreeNode parent){
        // 数空返回一个空
        if(p==null){
            return null;
        }else{
            // 寻找删除节点的位置
            if(p.key  > key){
                // 左节点寻找位置
                return removeBST(p.lchild, key, p);
            }else if(p.key < key){
                // 右节点寻找位置
                return removeBST(p.lchild, key, p);
            }else if(p.lchild!=null && p.rchild!=null) {
                // 待删除的左右节点均不为空
                BiTreeNode inNext=p.rchild;
                while(inNext.lchild!= null){
                    inNext = inNext.lchild;
                }
                p.data = inNext.data;
                p.key = inNext.key;
                return removeBST(p.rchild, p.key, p);
            }else{
                if(parent==null){
                    if(p.lchild!=null){
                        root = p.lchild;
                    }else {
                        root = p.rchild;
                    }
                    return p.data;
                }
                if(p==parent.lchild){
                    if(p.lchild!=null){
                        // 父节点的左子树为待删除节点
                        // 左子树必定小于父节点
                        // 优先让左子树来进行替代待删除节点保证树依旧为一个排序二叉树
                        parent.lchild = p.lchild;
                    }else {
                        parent.lchild = p.rchild;
                    }
                }else if(p==parent.rchild){
                    if(p.lchild!=null){
                        parent.rchild = p.lchild;
                    }else {
                        parent.rchild = p.rchild;
                    }
                }
                p.key = -1;
                return p.data;
            }
        }
    }



}
